#include <cstdio>
#include <cstring>

#define INF 0x3F3F3F3F
#define MAXN 500+5
#define MIN(a,b) (a<b?a:b)
#define MAX(a,b) (a>b?a:b)

int N;
int G[MAXN][MAXN];
int dis[MAXN];
bool vis[MAXN];
int ans;

void prim() {
	ans = 0;
	for (int i=1; i<=N; i++) {
		dis[i] = G[1][i];
	}
	memset(vis, 0, sizeof(vis));
	vis[1] = true;
	while (true) {
		bool flag = true;
		int u = 0;
		int min = INF;
		for (int i=1; i<=N; i++) {
			if (!vis[i]) {
				flag = false;
				if (dis[i] < min) {
					min = dis[i];
					u = i;
				}
			}
		}
		if (flag) break;
		ans = MAX(ans, min);
		vis[u] = true;
		for (int i=1; i<=N; i++) {
			if (!vis[i]) {
				dis[i] = MIN(dis[i], G[u][i]);
			}
		}
	}
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &N);
		//Input
		memset(G, 0x3F, sizeof(G));
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=N; j++) {
				scanf("%d", &G[i][j]);
				if (i==j) G[i][j] = INF;
			}
		}
		prim();
		printf("%d\n", ans);
	}
	return 0;
}
